Codeforces Round 655 Div2 A~D题解

闲话：这场居然因为queueforces unrated了，如果打了的话我应该出的了ABC
本场传送门：https://codeforces.com/contest/1372/

A. Omkar and Completion
题目大意：构造一个长度为$n$的数列$a$，使之满足任意两个数之和在数列里不存在。
分析：直接构造一个$11111..1111$的数列就可以了。

B. Omkar and Last Class of Math
题目大意：给定一个整数$n$，找到一组数对$(a,b)$满足$a+b=n$且$lcm(a,b)$最大。
数据范围：
$1 \leq T \leq 10$
$2 \leq n \leq 10^9$
分析：首先有两个变量，先消个元看一下：原式$lcm(a,n - a)$，由于$lcm$不怎么熟悉，就换成比较熟悉的$gcd$再看：原式=$\dfrac{a * (n - a)}{gcd(a,n - a)}$，发现下面这个$gcd$满足差分形式，即$gcd(a,n - a) = gcd(a,n)$，由于要使原式最大，故可以猜测一个结论：$a$的取值是$n$的最大约数，找出$n$的最小质因子$p$，$\frac{n}{p}$就是最大的约数了。
不过到此实际上还没解决问题（会WA4)，因为如果数$n$是个质数，那么他压根就没有任何的质因子，所以还需要特殊处理一下。由于$n$是一个质数，则任何小于$n$的数$a$与之互质，即$gcd(n,a)=1$，故原式=$a * (n - a)$，答案显然是当$a=1$是最小，输出即可。
代码：

using namespace std;
typedef long long ll;
const int N = 1e5+7;
int primes[N],cnt,st[N];
void init()
{
	for(int i = 2;i < N;++i)
	{
		if(!st[i])	primes[++cnt] = i;
		for(int j = 1;j <= cnt && i * primes[j] < N;++j)
		{
			st[i * primes[j]] = 1;
			if(i % primes[j] == 0)	break;
		}
	}
}
int main()
{
	init();
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
    	int ok = 0;
    	for(int i = 1;i <= cnt;++i)
    	{
    		if(n % primes[i] == 0)
    		{
    			printf("%d %d\n",n / primes[i],n - n / primes[i]);
    			ok = 1;
    			break;
    		}
    	}
    	if(!ok)
    	{
    		printf("%d %d\n",1,n - 1);
    	}
    }
    return 0;
}

C. Omkar and Baseball
题目大意：给定一个长度为$n$的数列$\{a\}$，且$\{a\}$是一组排列数，现在规定一种操作：每次可以选取一个区间，把区间内的数随意换位置，如果换完之后每个位置上的数都与原来的数不同，则可以进行这个操作，把新的数全换上去，否则不可以执行。问最少要几次可以完成对原数列的排序。
数据范围：
$1 \leq n \leq 2*10^5$
分析：首先由于数据范围很大，所以说最多也就遍历一次。手玩几组数据之后，一个大概的想法就是：开头和结尾已经有序的部分，肯定不用管了，所以要管的就是中间的部分。而中间这个部分可以分成两种情况：一种是中间有没有出现一个已经是有序的数，和中间完全是乱序的。
先看后面一种，我们可以发现如果中间完全是乱序的，只需要$1$次操作就可以解决问题了。
如果是前者，中间出现了一个有序的数，这时只需要额外再操作$1$次就可以解决问题了，第一步先把所有的其他数排好，之前有序的跟身边的一个交换一下位置，第二次把上次有序的和他旁边那个数再交换一下。
至此可以发现这个题的答案只有三种：$0,1,2$，贪心策略是正确的。直接去遍历一遍查中间是不是有已经有序的就行了。
代码：

using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		vector<int> a(n + 17),st(n + 17);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int flag = 0,last = -1;
		for(int i = 1;i <= n;++i)
		{
			if(a[i] != i)
			{
				if(flag == 0)	flag = 1,last = i;
				else if(flag == 1)
				{
					if(last == -1)	last = i;
					else if(last != i - 1)	flag = 2;
					
					if(flag != 2)	last = i;
				}
				// cout << flag << " " << last << endl;
			}
		}
		printf("%d\n",flag);
    }
    return 0;
}

D. Omkar and Circle
题目大意：给定一个长度为$n$，$n$是奇数的数列$\{a\}$，这个数列呈环状。每次可以选择环上的一个数，把这个数和他相邻的两个数删掉，用他相邻的两个数代替他。问最后整个环能得到的最大值是多少。
数据范围：
$1 \leq n \leq 2 *10^5$
$0 \leq a_i \leq 10^9$
注意答案爆$int$

分析：首先$n$的范围太大了，常规区间dp不可取。我们必须要有一个线性的做法。分析之后可以发现这个题最大的困难在于某个点$i$的值更新依赖于两边，而两边的贡献难算且很可能超复杂度，所以这个题必须要先做一步转换，看能不能消掉这个问题。
进而我们可以发现这个题是包装过的：用旁边两个数代替他，等价于把他自己删去，然后剩下的所有的数的和就是答案。形式化的语言来说明这个题目就是：在环上删掉$\frac{n}{2}$个不相邻的数，使最后剩下来的和最大。由于本题是一个环，所以我们先要想怎么拆环变数列：复制环成两倍是可以的，不过还有另外一种：先把$a_1$和$a_n$看做是断开的，就是他俩不能相连的情况算出第一个答案，那么还剩下一种情况：他俩相连应该是什么样的，这个问题之后再分析，因为他涉及到实际的题目情况，不过想到这里的时候基本可以敲定正确性了，往下做没什么问题。
在一个数列上做这个题的时候，如果暴力$dp$枚举有多少个数删去了转移肯定是不行的，还要找到一个可以快速计算出答案得性质：由于说整个数列长度$n$是个奇数，从里面扣$\frac{n}{2}$个数之后，会产生$\frac{n}{2}$个空隙，那么一共剩下了$\frac{n}{2} + 1$个数，故一定有两个没有被删的数是相邻的，并且只有一个。于是我们可以枚举所有可能情况：即枚举所有位置$i$，表示相邻的那两个数的右端点的下标是$i$，然后发现如果我们根据奇偶性来做前缀和的话，这个信息是非常好统计的，就可以以$O(1)$的代价算出删去的数的和了。于是复杂度就成功降到了$O(n)$。
现在我们回过头来看一下之前的那个问题：缺少的第二个条件该怎么补充。缺少的那个情况就是$a_1$和$a_n$没有相邻的情况，于是可以把$a_n$挪到$a_1$的前面，再做一次答案的求解过程，就可以把这种情况加上了。
分析完了具体该怎么分类之后，说明一下这个题该怎么实现。
首先这道题其实是一个原题（到这里来的话），题目是atcoder的abc_162F题，链接：https://atcoder.jp/contests/abc162/tasks/abc162_f
定义$f[x]$为开始到$x$依次选不相邻的数时的总和。
入口：$f[1] = a[1]$，其余为0
递推：$f[i] = f[i - 2] + a[i]$。
注意这个前缀和是隔了一位的，推式子的时候要注意其实际意义。
如果当前枚举的$i$是个奇数的话，答案是：$f[n - 1] - f[i - 1] + f[i - 2]$

如果当前枚举的$i$是个偶数的话，答案是：$f[i - 2] + f[n] - f[i - 1]$

最后，不要忘了做出另外一个数组$b$，再做一次。
当然，实际上$b$数组可以不用做满所有的操作，具体情况可以自己思考一下。
代码：

using namespace std;
typedef long long ll;
const int N = 2e5+7,INF = 1e9+7;
int a[N],b[N];
int n;
ll f[N];
ll slove(int c[])
{
	f[1] = c[1];
	// for(int i = 1;i <= n;++i)	cout << c[i] << " ";cout << endl;
	for(int i = 2;i <= n;++i)	f[i] = f[i - 2] + c[i];
	ll res = 1e18;
	for(int i = 2;i <= n;++i)
	{
		if(i % 2 == 0)
		{
			res = min(res,f[i - 2] + f[n] - f[i - 1]);
		}
		else
		{
			res = min(res,f[n - 1] - f[i - 1] + f[i - 2]);
		}
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	ll sum = 0;
	for(int i = 1;i <= n;++i)	scanf("%d",&a[i]),sum += a[i];
	if(n == 1)
	{
		printf("%d",a[1]);
		return 0;
	}
	ll res = 0;
	res = max(res,sum - slove(a));
	b[1] = a[n];
	for(int i = 2;i <= n;++i)	b[i] = a[i - 1];
	// for(int i = 1;i <= n;++i)	cout << b[i] << " ";cout << endl;
	res = max(res,sum - slove(b));
	printf("%lld",res);
    return 0;
}